import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;

/**
* @description: 剑指 Offer 33. 二叉搜索树的后序遍历序列
* @author hewei
* @date 2022/7/21 14:32
* @version 1.0
*/

public class VerifyPostorder {

    HashMap<Integer, Integer> map;
    int[] post;
    int[] mid;
    boolean flag = false;
    public boolean verifyPostorder1(int[] postorder) {
        int n = postorder.length;
        post = new int[n];
        map = new HashMap<>();
        System.arraycopy(postorder, 0, post, 0, n);
        Arrays.sort(postorder);
        mid = postorder;
        for (int i = 0; i < n; i++) {
            map.put(mid[i], i);
        }
        process(0, n - 1, 0, n - 1);
        return flag;
    }

    public void process(int ml, int mr, int pl, int pr) {
        if (ml > mr || pl > pr) return;
        int head = post[pr];
        Integer index = map.get(head);
        if (index > mr || index < ml) {
            flag = true;
            return;
        }
        process(ml, index - 1, pl, pl + index - ml - 1);
        process(index + 1, mr, pl + index - ml, pr - 1);
    }

    int[] postorder;
    public boolean verifyPostorder2(int[] postorder) {
        this.postorder = postorder;
        return dfs(0, postorder.length - 1);
    }

    public boolean dfs(int l, int r) {
        if (l >= r) return true;
        int m = l;
        while (postorder[m] < postorder[r]) ++m;
        int index = m;
        while (index < r) {
            if (postorder[index] < postorder[r]) break;
            ++index;
        }
        return index == r && dfs(l, m - 1) && dfs(m, r - 1);
    }

    public boolean verifyPostorder(int[] postorder) {
        Deque<Integer> stack = new LinkedList<>();
        int last = Integer.MAX_VALUE;
        for (int i = postorder.length - 1; i >= 0; i--) {
            if (postorder[i] > last) return false;
            while (!stack.isEmpty() && stack.peek() > postorder[i]) {
                last = stack.poll();
            }
            stack.push(postorder[i]);
        }
        return true;
    }
}
